package fun.ticsmyc.question.stringQuestion;

import org.junit.Test;

/**
 * O(N) 最长回文子串  马拉车算法
 *
 * @author Ticsmyc
 * @date 2020-04-06 12:12
 */
public class Manacher {

    private static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[charArr.length * 2 + 1];
        int index = 0;
        for (int i = 0; i < res.length; ++i) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    public static String maxLcpsLngth(String str) {
        if (str == null || str.length() < 1) {
            return "";
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length];  //每个位置的回文半径
        int index = 0;  //回文串中心位置
        int pR = -1;  //回文串右边界
        int max = Integer.MIN_VALUE;  //最长回文串长度
        int start =-1; //起始下标
        for (int i = 0; i < charArr.length; ++i) {

            //先确定一个初始的回文半径
            pArr[i] = i < pR ? Math.min(pArr[2 * index - i], pR - i) : 1;

            //向外扩
            while (i - pArr[i] >= 0 && i + pArr[i] < charArr.length) {
                if (charArr[i - pArr[i]] == charArr[i + pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            //判断是否需要更新回文边界
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                index = i;
            }

            if(pArr[i] > max){
                max = pArr[i]; //回文串长度为max-1  起始坐标是 (i-pArr[i]+1)/2
                start =(i-pArr[i]+1)/2;
            }

        }
        return str.substring(start,start+max-1);
    }

    @Test
    public void testManacherString() {
        String str = "how are you";
        char[] res = manacherString(str);
        for (char s : res) {
            System.out.print(s);
        }
    }

    @Test
    public void testManacher() {
        String str = "abc1234321ab";
        System.out.println(maxLcpsLngth(str));
    }

}
